{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Longest Arithmetic Subsequence of Given Difference"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: longestSubsequence"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最长定差子序列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>arr</code> 和一个整数 <code>difference</code>，请你找出并返回 <code>arr</code> 中最长等差子序列的长度，该子序列中相邻元素之间的差等于 <code>difference</code> 。</p>\n",
    "\n",
    "<p><strong>子序列</strong> 是指在不改变其余元素顺序的情况下，通过删除一些元素或不删除任何元素而从 <code>arr</code> 派生出来的序列。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [1,2,3,4], difference = 1\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>最长的等差子序列是 [1,2,3,4]。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [1,3,5,7], difference = 1\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>最长的等差子序列是任意单个元素。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [1,5,7,8,5,3,4,2,1], difference = -2\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>最长的等差子序列是 [7,5,3,1]。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= arr.length <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>-10<sup>4</sup> <= arr[i], difference <= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [longest-arithmetic-subsequence-of-given-difference](https://leetcode.cn/problems/longest-arithmetic-subsequence-of-given-difference/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [longest-arithmetic-subsequence-of-given-difference](https://leetcode.cn/problems/longest-arithmetic-subsequence-of-given-difference/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4]\\n1', '[1,3,5,7]\\n1', '[1,5,7,8,5,3,4,2,1]\\n-2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, arr: List[int], difference: int) -> int:\n",
    "        dp = {}\n",
    "        answer = 1\n",
    "        for a in arr:\n",
    "            before_a = dp.get(a - difference, 0)\n",
    "            dp[a] = before_a + 1\n",
    "            answer = max(answer, dp[a])\n",
    "            \n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, arr: List[int], difference: int) -> int:\n",
    "        d = defaultdict(int)\n",
    "        while arr:\n",
    "            x = arr.pop()\n",
    "            d[x] = d[x + difference] + 1\n",
    "        return max(d.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, arr: List[int], difference: int) -> int:\n",
    "        dp = {}\n",
    "        for num in arr:\n",
    "            dp[num] = 1\n",
    "            if num - difference in dp:\n",
    "                dp[num] = dp[num - difference] + 1\n",
    "        \n",
    "        return max(dp.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, arr: List[int], difference: int) -> int:\n",
    "        if not arr:\n",
    "            return 0\n",
    "        ans = 0\n",
    "        dp = dict()\n",
    "        for num in arr:\n",
    "            val = 0\n",
    "            val = dp.get(num - difference, 0) + 1\n",
    "            ans = max(ans, val)\n",
    "            dp[num] = val\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, arr: List[int], difference: int) -> int:\n",
    "        place=dict()\n",
    "        dp=[0 for i in range(len(arr))]\n",
    "        for i in range(len(arr)):\n",
    "            if arr[i]-difference in place:\n",
    "                dp[i]=dp[place[arr[i]-difference]]+1\n",
    "                place[arr[i]]=i\n",
    "            else:\n",
    "                dp[i]=1\n",
    "                place[arr[i]]=i\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, arr: List[int], difference: int) -> int:\n",
    "        Dic = {arr[0]:0}\n",
    "        F = [1 for a in range(len(arr))]\n",
    "        for a in range(1, len(arr)):\n",
    "            pre = arr[a]-difference \n",
    "            if pre in Dic.keys():\n",
    "                F[a] += F[Dic[pre]]\n",
    "            Dic[arr[a]] = a\n",
    "            #print([Dic, F])\n",
    "        \n",
    "        return max(F)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, arr: List[int], difference: int) -> int:\n",
    "        d = dict()\n",
    "        ans = 0\n",
    "        for a in arr:\n",
    "            if a - difference in d:\n",
    "                d[a] = d[a-difference] + 1\n",
    "            else:\n",
    "                d[a] = 1\n",
    "            ans = max(ans, d[a])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, arr: List[int], difference: int) -> int:\n",
    "        d = {}\n",
    "        for a in arr:\n",
    "            d[a] = d.get(a-difference,0)+1\n",
    "        return max(d.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, arr: List[int], difference: int) -> int:\n",
    "        d = defaultdict(int)\n",
    "        for num in arr:\n",
    "            d[num] = d[num - difference] + 1\n",
    "        return max(d.values())\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, arr: List[int], difference: int) -> int:\n",
    "        n=len(arr)\n",
    "        f0=[0]\n",
    "        f1=[1]\n",
    "        dt={}\n",
    "        dt[arr[0]]=0\n",
    "        for i in range(1,n):\n",
    "            f0.append(max(f0[i-1],f1[i-1]))\n",
    "            a=arr[i]\n",
    "            bf=a-difference\n",
    "            if bf in dt.keys():\n",
    "                f1.append(f1[dt[bf]]+1)\n",
    "            else:\n",
    "                f1.append(1)\n",
    "            dt[a]=i\n",
    "\n",
    "        return max(f0[n-1],f1[n-1])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, arr: List[int], difference: int) -> int:\n",
    "        # result = [1 for i in arr]\n",
    "        count = {}\n",
    "        for i in range(len(arr)):\n",
    "            if(arr[i] - difference in count):\n",
    "                count[arr[i]] = count[arr[i] - difference] + 1\n",
    "            else:\n",
    "                count[arr[i]] = 1\n",
    "        # print(count)\n",
    "        return max(count.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, arr: List[int], difference: int) -> int:\n",
    "        d = dict()\n",
    "        for i in range(len(arr)):\n",
    "            if arr[i]-difference not in d.keys():\n",
    "                d[arr[i]] = 1\n",
    "                continue\n",
    "            d[arr[i]] = d[arr[i]-difference]+1\n",
    "        print(d)\n",
    "        return max(d.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, arr: List[int], difference: int) -> int:\n",
    "        dp = Counter()\n",
    "        for v in arr:\n",
    "            dp[v] = dp[v - difference] + 1\n",
    "        return max(dp.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, arr: List[int], difference: int) -> int:\n",
    "        if not arr:return 0\n",
    "        n =len(arr)\n",
    "        # dp =[1]*n\n",
    "        # # 18 / 41 个通过的测试用例\n",
    "        # alist =[]\n",
    "        # for i in range(1,n):\n",
    "        #     for j in range(i):\n",
    "\n",
    "        #         if arr[i]-arr[j]==difference:\n",
    "        #             dp[i] =max(dp[i],dp[j]+1)\n",
    "        #         else:\n",
    "        #             dp[i] =max(dp[i],dp[j])\n",
    "        ans ={}\n",
    "        for i in arr:\n",
    "            if i-difference in ans:\n",
    "                ans[i] =ans[i-difference]+1\n",
    "            else:\n",
    "                ans[i] =1\n",
    "        return max(ans.values())\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, arr: List[int], difference: int) -> int:\n",
    "        #copy\n",
    "        subsequence = defaultdict(int)\n",
    "        for num in arr:\n",
    "            subsequence[num]= subsequence[num-difference] +1\n",
    "        return max(subsequence.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, arr: List[int], difference: int) -> int:\n",
    "        d=defaultdict(int)\n",
    "        res=0\n",
    "        for a in arr:\n",
    "            d[a]=max(d[a],d[a-difference]+1)\n",
    "            res=max(res,d[a])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, arr: List[int], difference: int) -> int:\n",
    "        n = len(arr)\n",
    "        dp = [1] * n\n",
    "        index = {arr[0]: 0}\n",
    "        last = [-1] * n\n",
    "        for i in range(1, n):\n",
    "            if arr[i] - difference in index: last[i] = index[arr[i] - difference]\n",
    "            index[arr[i]] = i  \n",
    "        for i in range(1, n): \n",
    "            if last[i] != -1:\n",
    "                dp[i] += dp[last[i]]\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, arr: List[int], difference: int) -> int:\n",
    "        # dp[i]表示前i个的最长 - 1\n",
    "        n = len(arr)\n",
    "        dp = [0] * n\n",
    "        # 用哈希表存i前面的所有数的索引\n",
    "        idxhashtable = defaultdict(list)\n",
    "        idxhashtable[arr[0]].append(0)\n",
    "\n",
    "        # 找到前面的对应的数的idx\n",
    "        for i in range(1, n):\n",
    "            for idx in idxhashtable[arr[i] - difference]:\n",
    "                dp[i] = max(dp[i], dp[idx] + 1)\n",
    "            idxhashtable[arr[i]].append(i)\n",
    "        \n",
    "        return max(dp) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, arr: List[int], difference: int) -> int:\n",
    "        s = set()\n",
    "        dp = collections.defaultdict(int)\n",
    "        for num in arr:\n",
    "            if num - difference in s:\n",
    "                dp[num] = max(dp[num], dp[num - difference] + 1)\n",
    "            s.add(num)\n",
    "        if dp:\n",
    "            return max(dp.values()) + 1\n",
    "        else:\n",
    "            return 1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, arr: List[int], difference: int) -> int:\n",
    "        n = len(arr)\n",
    "        f = [[0] * 2 for _ in range(1 + n)]\n",
    "        ##f[1][1] = 1\n",
    "        dic = {}\n",
    "        for i in range(1, 1 + n):\n",
    "            f[i][0] = max(f[i - 1][0], f[i - 1][1])\n",
    "            f[i][1] = max(f[i][1], dic.get(arr[i - 1] - difference, 0) + 1)\n",
    "            dic[arr[i - 1]] = f[i][1]\n",
    "\n",
    "        return max(f[n])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, arr: List[int], difference: int) -> int:\n",
    "        n = len(arr)\n",
    "        mp = defaultdict(int)\n",
    "        dp = [[0]*2 for _ in range(n)]\n",
    "        dp[0][0] = 0 #不选择当前数字\n",
    "        dp[0][1] = 1 #不选择当前数字\n",
    "        mp[arr[0]]=1\n",
    "        for i in range (1,n):\n",
    "            dp[i][0] = max(dp[i-1][0],dp[i-1][1])\n",
    "            dp[i][1] = 1\n",
    "            pre = arr[i]-difference\n",
    "            if pre in mp:\n",
    "                dp[i][1] = mp[pre]+1\n",
    "            mp[arr[i]]=dp[i][1]\n",
    "        return max(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, arr: List[int], difference: int) -> int:\n",
    "        n = len(arr); dp = [1] * n; index = defaultdict(list)\n",
    "        for i, v in enumerate(arr):\n",
    "            index[v].append(i)\n",
    "        for i in range(1, n):\n",
    "            v = arr[i]\n",
    "            w = v - difference\n",
    "            for j in index[w]:\n",
    "                if j >= i: break\n",
    "                dp[i] = max(dp[i], dp[j] + 1)\n",
    "        return max(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, a: List[int], dd: int) -> int:\n",
    "        n=len(a)\n",
    "        d=defaultdict(list)\n",
    "        ans=0\n",
    "        for i,c in enumerate(a):\n",
    "            d[c].append(i)\n",
    "        dp=[0]*n\n",
    "        ans=1\n",
    "        for i in range(1, n):\n",
    "            tt=a[i]-dd\n",
    "            if tt in d:\n",
    "                t0=bisect_left(d[tt], i)-1\n",
    "                t=d[tt][t0]\n",
    "                if t<i:\n",
    "                    dp[i]=max(2, dp[t]+1)\n",
    "                    ans=max(ans, dp[i])\n",
    "        return ans\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
